package leetcode.daily;

import java.util.*;

/**
 * @author : zx
 * @version V1.0
 */
public class med_easy_20201217 {


    /**
     * 669. 修剪二叉搜索树
     * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
     *
     * 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
     *
     *
     *
     * 示例 1：
     *
     *
     * 输入：root = [1,0,2], low = 1, high = 2
     * 输出：[1,null,2]
     * 示例 2：
     *
     *
     * 输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
     * 输出：[3,2,null,1]
     * 示例 3：
     *
     * 输入：root = [1], low = 1, high = 2
     * 输出：[1]
     * 示例 4：
     *
     * 输入：root = [1,null,2], low = 1, high = 3
     * 输出：[1,null,2]
     * 示例 5：
     *
     * 输入：root = [1,null,2], low = 2, high = 4
     * 输出：[2]
     *
     *
     * 提示：
     *
     * 树中节点数在范围 [1, 104] 内
     * 0 <= Node.val <= 104
     * 树中每个节点的值都是唯一的
     * 题目数据保证输入是一棵有效的二叉搜索树
     * 0 <= low <= high <= 104
     */
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return root;
        if(root.val > high) return trimBST(root.left, low, high);
        if(root.val < low) return trimBST(root.right, low, high);
        if(root.left!=null) root.left = trimBST(root.left, low, high);
        if(root.right!=null) root.right = trimBST(root.right, low, high);
        return root;
    }

    /**
     * 609. 在系统中查找重复文件
     * 给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。
     *
     * 输入列表中的单个目录信息字符串的格式如下：
     *
     * "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"
     *
     * 这意味着有 n 个文件（f1.txt, f2.txt ... fn.txt 的内容分别是 f1_content, f2_content ... fn_content）在目录 root/d1/d2/.../dm 下。注意：n>=1 且 m>=0。如果 m=0，则表示该目录是根目录。
     *
     * 该输出是重复文件路径组的列表。对于每个组，它包含具有相同内容的文件的所有文件路径。文件路径是具有下列格式的字符串：
     *
     * "directory_path/file_name.txt"
     *
     * 示例 1：
     *
     * 输入：
     * ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
     * 输出：
     * [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
     *
     *
     * 注：
     *
     * 最终输出不需要顺序。
     * 您可以假设目录名、文件名和文件内容只有字母和数字，并且文件内容的长度在 [1，50] 的范围内。
     * 给定的文件数量在 [1，20000] 个范围内。
     * 您可以假设在同一目录中没有任何文件或目录共享相同的名称。
     * 您可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用一个空格分隔。
     *
     *
     * 超越竞赛的后续行动：
     *
     * 假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？
     * 如果文件内容非常大（GB级别），您将如何修改您的解决方案？
     * 如果每次只能读取 1 kb 的文件，您将如何修改解决方案？
     * 修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？
     * 如何确保您发现的重复文件不是误报？
     */
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> m = new HashMap();
        for(String s : paths){
            String[] ss = s.split(" ");
            String dir = ss[0];
            for(int i = 1; i < ss.length; i++){
                String fileName = ss[i].substring(0, ss[i].indexOf("("));
                String content = ss[i].substring(ss[i].indexOf("(")+1, ss[i].indexOf(")"));
                List<String> l = m.get(content);
                if(l == null){
                    l = new ArrayList<>();
                    l.add(dir+"/"+fileName);
                    m.put(content, l);
                }else{
                    l.add(dir+"/"+fileName);
                }
            }
        }
        List<List<String>> res = new ArrayList<>();
        for (List<String> l : m.values()){
            if(l.size() <= 1) continue;
            res.add(l);
        }
        return res;
    }

    /**
     * 1424. 对角线遍历 II
     * 给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：nums = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[1,4,2,7,5,3,8,6,9]
     * 示例 2：
     *
     *
     *
     * 输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
     * 输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
     * 示例 3：
     *
     * 输入：nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
     * 输出：[1,4,2,5,3,8,6,9,7,10,11]
     * 示例 4：
     *
     * 输入：nums = [[1,2,3,4,5,6]]
     * 输出：[1,2,3,4,5,6]
     *
     *
     * 提示：
     *
     * 1 <= nums.length <= 10^5
     * 1 <= nums[i].length <= 10^5
     * 1 <= nums[i][j] <= 10^9
     * nums 中最多有 10^5 个数字。
     *
     */
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        int length = nums.size();
        int[][] num = new int[length][];
        Iterator<List<Integer>> iterator = nums.iterator();
        for(int i = 0; i < length && iterator.hasNext(); i++){
            List<Integer> l = iterator.next();
            Iterator<Integer> iter = l.iterator();
            num[i] = new int[l.size()];
            for(int j = 0; iter.hasNext(); j++){
                num[i][j] = iter.next();
            }
        }
        List<Integer> result = new ArrayList<>();
        for(int i = 0; i < length; i++){
            int r = i;
            int l = 0;
            for( ; r >= 0; r--,l++){
                int[] li = num[r];
                if(li.length > l) result.add(li[l]);
            }
        }
        for(int r = length-1, l = 1; r >= 0; ){
            if(l >= num[r].length){
                r--;
                l++;
                continue;
            }
            for( int i = r, j = l; i >= 0; i--, j++){
                int[] li = num[i];
                if(li.length > j) result.add(li[j]);
            }
            l++;
        }
        int[] res = new int[result.size()];
        Iterator<Integer> iter = result.iterator();
        for(int i = 0; iter.hasNext(); i++){
            res[i] = iter.next();
        }
        return res;
    }
    public int[] findDiagonalOrder1(List<List<Integer>> nums) {
        int length = 0;
        //根据对角线i+j唯一且相同，LinkedHashMap保持插入排序。效率是最优的
        Map<Integer,List<Integer>> map =new LinkedHashMap<>();
        for(int i = 0;i < nums.size();i++) {
            length += nums.get(i).size();
            for(int j = 0;j < nums.get(i).size();j++) {
                List<Integer> orDefault = map.getOrDefault(i + j, new ArrayList<>());
                orDefault.add(nums.get(i).get(j));
                map.putIfAbsent(i+j,orDefault);
            }
        }
        int[] result = new int[length];
        int index = 0;
        //遍历map，得到结果。
        for(int key : map.keySet()) {
            List<Integer> list = map.get(key);
            for(int j = list.size() - 1;j >= 0;j--) {
                result[index] = list.get(j);
                index++;
            }
        }
        return result;
    }


    public int numEquivDominoPairs(int[][] dominoes) {
        int len = dominoes.length;
        int[][] first = new int[len][2];
        int[][] second = new int[len][2];
        System.arraycopy(dominoes, 0, first, 0, len);
        second = dominoes;
        Arrays.sort(first, ((o1, o2) -> {return o1[0]-o2[0];}));
        Arrays.sort(second, ((o1, o2) -> {return o1[1]-o2[1];}));
        int result = 0;
        int tail = 0;
        int d = 0;
        for(int i = 0; i < len; i++){
            for(int j = i+1; j < len ;j++){
                if(first[j][0] == first[i][0]){
                    if(first[j][1] == first[i][1]) result++;
                }else {
                    break;
                }
            }
            while (second[tail][1] < first[i][0] && tail < len-1){
                tail++;
            }
            for(int j = tail; j < len; j++){
                if(second[j][1] == first[i][0]){
                    if(second[j][0] == first[i][1] && first[i][0] != first[i][1]) {
                        result++;
                        d++;
                    }
                }else {
                    break;
                }
            }
        }
        return result-d/2;
    }
}
